package 堆排序;

import java.util.Arrays;

public class 堆排序 {
	public static void main(String[] args) {
		
//		int arr[] = {4,6,8,5,9};
//		
//		//堆排序
//		HeapSort heapSort = new HeapSort();
//		heapSort.heapSort(arr);
//		System.out.println(Arrays.toString(arr));
		
		HeapSort heapSort = new HeapSort();
		
		int[] longInt = new int[80000];
		for (int i = 0; i < longInt.length; i++) {
			longInt[i] = (int) (Math.random()*10000);
		}
		
		//O(nlogn)，-20+
		
		long star = System.currentTimeMillis();
		heapSort.heapSort(longInt);
		long end = System.currentTimeMillis();
		
		System.out.println((end-star) + "毫秒");
		System.out.println((end-star)/1000 + "秒");//1s
	}
}

/**
 * 堆排序
 * @author PC
 *
 */
class HeapSort{
	
	/**
	 * 堆排序
	 */
	public void heapSort(int[] arr) {
		int temp = 0;
		System.out.println("堆排序...");
		//测试
//		adjustHeap(arr, 1, arr.length);
//		System.out.println(Arrays.toString(arr));//[4, 9, 8, 5, 6]
		
		//1.构建大顶堆
		//循环找到非子结点
		for(int i = arr.length/2-1; i >= 0; i--) {
			adjustHeap(arr, i, arr.length);
		}
		//2.调整堆结构+交换堆顶元素与末尾元素
		//将堆顶结点（最大值）与末尾元素交换，然后在调整大顶堆
		for(int j = arr.length -1; j > 0; j--) {
			temp = arr[j];
			arr[j] = arr[0];
			arr[0] = temp;
			//交换之后破坏了大堆顶结构，从上向下调整？
			adjustHeap(arr, 0, j);
		}
	}
	
	/**
	  *  调整大顶堆，非叶子结点大于左右子结点
	 * @param arr 待排序数组
	 * @param i 开始时叶子结点
	 * @param length 待排序个数，逐渐减少
	 */
	public void adjustHeap(int arr[],int i,int length) {
		
		//取出当前元素的值，保存待用
		int temp = arr[i];
		
		//开始调整
		/*
		 * 找到左子结点：k = 2*i+1 
		 * 找到右子结点：k = (2*i+1)+1 = k+1
		 * 每次循环都是找下一个左子结点
		 */
		for(int k = 2*i+1;k < length ; k = 2*k+1) {
			//比较左右子结点，找到最大的，且k+1不越界
			if(k+1 < length && arr[k] < arr[k+1]) {
				k++;
			}
			
			//比较父子结点，子大则交换（这里只赋值）
			if(temp < arr[k]) {
				//赋值，两相同
				arr[i] = arr[k];
				//把大的结点位置交给i，下次从大的结点那里开始
				i = k;
			}else {
				//自不大于父，不交换，进行下一个结点比较
				break;
			}
			//比较结束后，i是三个节点中最小的，把当前遍历的非叶子结点赋给i的位置
			arr[i] = temp;
		}
	}
}